// Find optimal time pattern for theorem solvers using genetic algorithm
// Version 1.0

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>

using namespace std;

// Input Parameters
short NUM_OF_SOLVERS; 
short NUM_OF_PROBLEMS;
double TIME_LIMIT;
vector<vector<double> > table;

// Genetic Algorithm Parameters
const short PIECES = 500;     // Divide the time period into PIECES parts.
const short POPULATION_SIZE = 3000;   // Number of Chromosomes Generated.

const double CROSSOVER_PROB = 0.01;
const double MUTATE_PROB = 0.005;

// Random Number Generation Functions
#define RANDINIT()	srand(time(NULL))
#define RANDOM()	((float)rand() / (float)RAND_MAX)
#define RANDMAX(x)	(int)((float)(x)*rand()/(RAND_MAX+1.0)) // [0,x)

#define swap(a,b) {a^=b;b^=a;a^=b;}

/*
// Time Control Functions
#ifdef _MSC_VER
#include <ctime>
double startTime;
void startTime() { startTime = clock(); }
double getTime() { return ((double)(clock())-startTime) / CLOCKS_PER_SEC; }
#else
#include <sys/time.h>
double startTime;
void startTime() { timeval t; gettimeofday(&t,0); startTime = (double)(t.tv_sec) + (double)(t.tv_usec) / 1000000.0; }
double getTime() { timeval t; gettimeofday(&t,0); double endTime = (double)(t.tv_sec) + (double)(t.tv_usec) /1000000.0; return endTime-startTime; }
#endif
*/

// Definition of the Chromosome Type
typedef struct {
    short color[PIECES];
    int fitness;
} chromosome_t;

class SolversTiming{
public:

    int iteration;
    
    int max, min, sum;
    double avg;
    
    chromosome_t chromosomes[2][POPULATION_SIZE];
    
    double compute_fitness( int cur_pop, int member ){

        int fitness = 0;
        bool successFlag;     // Mark whether a problem is solved.
        vector<int> timeCounter;
        for (int i = 0 ; i < NUM_OF_SOLVERS ; i ++)
            timeCounter.push_back(0);
        for (int i = 0 ; i < PIECES ; i ++)
            timeCounter[ chromosomes[cur_pop][member].color[i] ] ++;
        for (int i = 0 ; i < NUM_OF_PROBLEMS ; i ++){
            successFlag = false;
            for (int j = 0 ; j < NUM_OF_SOLVERS ; j ++){
                if ( timeCounter[j] * TIME_LIMIT >= table[j][i] * PIECES ){
                    successFlag = true; break;
                }
            }
            if (successFlag) {fitness ++;}
        }

        return fitness;
    }
    
    void compute_population_fitness( int cur_pop ){

        int fitness;
        sum = 0;
        min = 100000;
        max = 0;
        for (int i = 0 ; i < POPULATION_SIZE ; i++) {
            fitness = compute_fitness( cur_pop, i );
            sum += fitness;
            if (fitness > max) max = fitness;
            if (fitness < min) min = fitness;
            chromosomes[cur_pop][i].fitness = fitness;
        }
        avg = (double)sum / (double)POPULATION_SIZE;
    }
    
    void initialize_member( int cur_pop, int member ){

        for (int i = 0 ; i < PIECES ; i ++)
            chromosomes[cur_pop][member].color[i] = RANDMAX(NUM_OF_SOLVERS);
        chromosomes[cur_pop][member].fitness = 0;
    }

    void initialize_population( int cur_pop ){

        int fixedNum;  // number of pieces that are fixed to some given color       
        int period = POPULATION_SIZE / NUM_OF_SOLVERS;
        int member = 0;

        for (int i = 0 ; i < NUM_OF_SOLVERS; i ++){
            for (int j = 1 ; j <= period; j ++){
                fixedNum = PIECES * j / period;
                for (int k = 0 ; k < PIECES; k ++)
                    chromosomes[cur_pop][member].color[k] = 
                     (k < fixedNum) ? i : RANDMAX(NUM_OF_SOLVERS);
                chromosomes[cur_pop][member++].fitness = 0;
            }        
        }

        // The remaining population (randomly chosen)
        int remain = POPULATION_SIZE - NUM_OF_SOLVERS * period;
        for (int i = 0 ; i < remain ; i++)
            initialize_member( cur_pop, member++ );
        
    }
    
    int select_parent( int cur_pop ){

        int i = RANDMAX(POPULATION_SIZE);
        int count = POPULATION_SIZE;
        int select = 0;

        while (count--) {
            select = chromosomes[cur_pop][i].fitness;
            if (select >= avg) return i;
            if (++i >= POPULATION_SIZE) i = 0;
        }

        return( RANDMAX(POPULATION_SIZE) );
    }

    int evolve( int cur_pop ){
        
        int new_pop = (cur_pop == 0) ? 1 : 0;
        int parent_1, parent_2;

        for (int i = 0 ; i < POPULATION_SIZE ; i += 2 ) {

            parent_1 = select_parent(cur_pop);
            parent_2 = select_parent(cur_pop);

            // Perform Crossover
            if ( RANDOM() < CROSSOVER_PROB ) {
                int crossPoint = RANDMAX(PIECES);
                for (int j = 0 ; j <= crossPoint ; j ++){
                    swap(chromosomes[cur_pop][parent_1].color[j],
                      chromosomes[cur_pop][parent_2].color[j]);
                }
            }

            // Perform Mutate
            if ( RANDOM() < MUTATE_PROB ){
                int mutatePoint1 = RANDMAX(PIECES);
                int mutatePoint2 = RANDMAX(PIECES);
                chromosomes[cur_pop][parent_1].color[mutatePoint1] = RANDMAX(NUM_OF_SOLVERS); 
                chromosomes[cur_pop][parent_2].color[mutatePoint2] = RANDMAX(NUM_OF_SOLVERS);
            }

            chromosomes[new_pop][i] = chromosomes[cur_pop][parent_1];
            chromosomes[new_pop][i + 1] = chromosomes[cur_pop][parent_2];

        }
        return new_pop;
    }
    
    vector<short> best( int cur ){

        int bestFitness = chromosomes[cur][0].fitness;
        int bestChromosome = 0;
        vector<short> timePattern;

        for (int i = 1 ; i < POPULATION_SIZE ; i++) {
            if (chromosomes[cur][i].fitness > bestFitness) {
              bestFitness = chromosomes[cur][i].fitness;
              bestChromosome = i;
            }
        }

        cout<<"Iteration : "  << iteration << endl; 
        cout << "The Best Fitness is : " << bestFitness << endl;
 
        timePattern.assign(chromosomes[cur][bestChromosome].color, 
         chromosomes[cur][bestChromosome].color + PIECES);
        
        return timePattern;
    }
    
    vector<short> findTimePattern(){

        int cur = 0;

        // starttime();

        RANDINIT();

        initialize_population( cur );
        compute_population_fitness( cur );

        iteration = 0;

        while(iteration < 1000){

            iteration ++;

            cur = evolve( cur );
            compute_population_fitness( cur );

            // if ( gettime() > 9 ) break;
        }

        return best(cur);
    }
};


int main(){

    freopen("ga.in","r",stdin);freopen("ga.out","w",stdout);

    SolversTiming st;
    vector<short> result;
    vector<double> line;
    double time;

    // Reading The Constants
    cin >> NUM_OF_SOLVERS; 
    cin >> NUM_OF_PROBLEMS;
    cin >> TIME_LIMIT;

    // Reading The Table
    for (int i = 0; i < NUM_OF_SOLVERS; i ++ ){
        for (int j = 0; j < NUM_OF_PROBLEMS; j ++ ){
            cin >> time;
            line.push_back(time);             
        }
        table.push_back(line);
        line.clear();
    }

    result = st.findTimePattern();

    vector<int> timeCounter;

    for (int i = 0 ; i < NUM_OF_SOLVERS ; i ++)
        timeCounter.push_back(0);
    for (int i = 0 ; i < PIECES ; i ++)
        timeCounter[ result[i] ] ++;
    for (int i = 0 ; i < NUM_OF_SOLVERS ; i ++)
        cout << i << " " << (double)timeCounter[i] * (double)TIME_LIMIT / (double)PIECES << endl;

    cout << flush;

    return 0;
}


